package cn.oder.insert;

import cn.oder.Sorted;
import cn.oder.SortedBase;
import cn.oder.enums.Sore;
import lombok.Getter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * 类简介: 希尔排序
 * 概念：根据增量序列进行排序，当增量序列递减到0的时候排序结束
 * 时间复杂度是O（n^1.3）,时间复杂度为O(1),不稳定的
 *
 * @Author: ShangGuan
 * @Time: 2024/05/16
 **/
@Getter
public class HibbardSorted extends SortedBase implements Sorted {

    private static final Logger log = LoggerFactory.getLogger(HibbardSorted.class);
    private final int length;

    private final List<Integer> sequence;


    public HibbardSorted(List<Integer> arr, Sore sore) {
        super(sore, arr);
        this.length = arr.size();
        this.sequence = generateSequence();
    }

    public HibbardSorted(List<Integer> arr) {
        super(arr);
        this.length = arr.size();
        this.sequence = generateSequence();
    }

    /**
     * 生成增量序列
     * 方法简介:希尔增量序列的生成过程使用了Hibbard增量序列的公式 2^K-1 ，其中k=0,1,2,...，直到增量大于等于数组大小的一半为止。
     *
     * @return {@link List }<{@link Integer }>
     **/
    public List<Integer> generateSequence() {
        List<Integer> sequence = new ArrayList<>();
        int k = 1;
        while (Math.pow(2, k) - 1 < length / 2) {
            sequence.add((int) (Math.pow(2, k) - 1));
            k++;
        }
        log.info("Hibbard增量序列为：{}", sequence);
        return sequence;
    }

    @Override
    public List<Integer> sort() {
        int n = arr.size();
        // 初始化增量为 n/2，不断缩小增量直到 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr.get(i);
                int j = i;
                if (sore.equals(Sore.ASC)) {
                    while (j >= gap && arr.get(i - gap) > temp) {
                        arr.set(j, arr.get(j - gap));
                        j -= gap;
                    }
                } else {
                    while (j >= gap && arr.get(j - gap) < temp) {
                        arr.set(j, arr.get(j - gap));
                        j -= gap;
                    }
                }
                arr.set(j, temp);
            }
        }
        return arr;

    }


}
